package com.leet.grapth;

import java.util.*;

public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ans = new int[numCourses];
        int[] inDegree = new int[numCourses];
        Arrays.fill(inDegree,0);
        List<List<Integer>> neigh = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0 ;i < numCourses; i++){
            neigh.add(new ArrayList<>());
        }
        for(int[] relation :prerequisites){
            neigh.get(relation[1]).add(relation[0]);
            inDegree[relation[0]]++;
        }
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0) q.offer(i);
        }
        if(q.size() == 0) return new int[0];
        int j = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0 ; i < size; i++){
                Integer head = q.poll();
                ans[j++] = head;
                for(Integer next:neigh.get(head)){
                    inDegree[next]--;
                    if(inDegree[next] == 0) q.offer(next);
                }
            }
        }
        if(j != numCourses) return new int[0];
        return ans;
    }
}
